package com.ctrip.study.algorithm.pratice;

import java.util.Arrays;

import junit.framework.TestCase;

import org.junit.Test;

public class SearchMinK extends TestCase{
	
	@Test
	public void test(){
		int[] array = {8,29,35,51,69,22,71,36,12};
		searchMin(array, 4);
	}

	/**
	 * 寻找k个最小值.
	 *
	 * @param array the array
	 * @param k the k
	 */
	private void searchMin(int[] array, int k) {
		solution2(array, k);
	}

	
	/**
	 * 当然，更好的办法是维护k个元素的最大堆，
	 * 即用容量为k的最大堆存储最先遍历到的k个数，
	 * 并假设它们即是最小的k个数，
	 * 建堆费时O（k）后，有k1<k2<...<kmax（kmax设为大顶堆中最大元素）。
	 * 继续遍历数列，每次遍历一个元素x，
	 * 与堆顶元素比较，x<kmax，更新堆（用时logk），否则不更新堆。
	 * 这样下来，总费时O（k+（n-k）*logk）=O（n*logk）。
	 * 此方法得益于在堆中，查找等各项操作时间复杂度均为logk
	 */
	private void solution2(int[] array, int k) {
		int[] minArray = new int[k];
		for (int i = 0; i < k; i++) {
			minArray[i] = array[i];
		}
		buildMaxHeap(minArray);
		for (int i = k; i < array.length; i++) {
			if(array[i] < minArray[0]){
				minArray[0] = array[i];
				adjust(0, minArray);
			}
		}
		System.out.println(Arrays.toString(minArray));
	}
	
	
	
	private void buildMaxHeap(int[] minArray) {
		//取得数组总长度，及堆最大的序号
		int maxIndex = minArray.length;
		System.out.println("Before sort: " + Arrays.toString(minArray));
		//这是建堆的过程，一次从倒数第二层的根节点开始调整堆，
		//即数组下标为i/2 - 1开始，一直到顶层根节点
		for (int i = maxIndex / 2 - 1; i >= 0; i--) {
			//对有孩子节点的元素进行调整
			adjust(i, minArray);
		}
		System.out.println("After sort: " + Arrays.toString(minArray));
	}

	private void adjust(int currIndex, int[] array) {
		//获取该节点的左孩子下标
		int leftIndex = leftIndex(currIndex);
		//获取该节点的右孩子下标
		int rightIndex = rightIndex(currIndex);
		//临时变量，存储当前currIndex、leftIndex、rightIndex最大值下标
		int maxIndex = currIndex;
		// 存在左结点，且左结点的值大于根结点的值  
        if (leftIndex < array.length && array[leftIndex] > array[currIndex]){
        	maxIndex = leftIndex;
        }
        // 存在右结点，且右结点的值大于以上比较的较小值  
        if (rightIndex < array.length && array[rightIndex] > array[maxIndex]){
        	maxIndex = rightIndex;
        }
        if(currIndex == maxIndex){
        	return;
        }
        //最大值替换根节点  
        swap(currIndex, maxIndex, array);
        // 由于替换后左右子树会被影响，所以要对受影响的子树再进行heapify  
        adjust(maxIndex, array);
	}
	

	/**
	 * 交换.
	 *
	 * @param currIndex the curr index
	 * @param maxIndex the max index
	 * @param array the array
	 */
	private void swap(int a, int b, int[] array) {
		int temp = array[a];
		array[a] = array[b];
		array[b] = temp;
	}

	/**
	 * 获取该节点的左孩子下标.
	 *
	 * @param currIndex the curr index
	 * @return the int
	 */
	private int leftIndex(int currIndex) {
		return currIndex * 2 + 1;
	}
	
	
	/**
	 * 获取该节点的右孩子下标.
	 *
	 * @param currIndex the curr index
	 * @return the int
	 */
	private int rightIndex(int currIndex) {
		return currIndex * 2 + 2;
	}

	/**
	 * 排序，选择排序。用选择或交换排序，即遍历n个数，
	 * 先把最先遍历到得k个数存入大小为k的数组之中，
	 * 对这k个数，利用选择或交换排序，
	 * 找到k个数中的最大数kmax（kmax设为k个元素的数组中最大元素），
	 * 用时O（k），
	 * 后再继续遍历后n-k个数，
	 * x与kmax比较：如果x<kmin，则x代替kmax，
	 * 并再次重新找出k个元素的数组中最大元素kmax；
	 * 如果x>kmax，则不更新数组。
	 * 这样，每次更新或不更新数组的所用的时间为O（k）或O（0），
	 * 整趟下来，总的时间复杂度平均下来为：n*O（k）=O（n*k）。.
	 */
	private void solution1(int[] array, int k) {
		int[] minArray = new int[k];
		for (int i = 0; i < array.length; i++) {
			if(i < k){
				minArray[i] = array[i];
			}else{
				//寻找一个数组中的最大值下标
				int maxIndex = searchMax(minArray);
				if(array[i] < minArray[maxIndex]){
					minArray[maxIndex] = array[i];
				}
			}
		}
		System.out.println(Arrays.toString(minArray));
	}

	/**
	 * 寻找一个数组中最大的数下标.
	 *
	 * @param minArray the min array
	 * @return the int
	 */
	private int searchMax(int[] minArray) {
		int maxIndex = 0;
		for (int i = 1; i < minArray.length; i++) {
			maxIndex = minArray[i] > minArray[maxIndex] ? i : maxIndex;
		}
		return maxIndex;
	}
	

}
